#include<iostream>
using namespace std;
#define N 10
int tag[10][10];

int cal_edit_dis(char* strA,int beginA,int endA,char* strB,int beginB,int endB){
    if(beginA>endA){
        if(beginB>endB)
            return 0;
        else
            return endB-beginB+1;
    }
    if(beginB>endB){
        if(beginA>endA)
            return 0;
        else
            return endA-beginA+1;
    }

    if(strA[beginA]==strB[beginB]){
        if(tag[beginA][beginB]==0)
            return tag[beginA][beginB];
        else{
            return cal_edit_dis(strA,beginA+1,endA,strB,beginB+1,endB);
        }
    }else{
        int t1,t2,t3,t4;
        if(tag[beginA][beginB+1]==0)
            t1 = cal_edit_dis(strA,beginA,endA,strB,beginB+1,endB);
        else
            t1 = tag[beginA][beginB+1];
        if(tag[beginA+1][beginB]==0)
            t2 = cal_edit_dis(strA,beginA+1,endA,strB,beginB,endB);
        else
            t2 = tag[beginA+1][beginB];
        if(tag[beginA+1][beginB+1]==0)
            t3 = cal_edit_dis(strA,beginA+1,endA,strB,beginB+1,endB);
        else
            t3 = tag[beginA+1][beginB+1];
        t4 = t1<t2?t1:t2;
        return (t4<t3?t4:t3)+1;
    }
}

int main(){
    char strA[] = "abdefg";
    char strB[] = "nbcdefg";
    memset(tag,0,sizeof(tag));
    cout << cal_edit_dis(strA,0,sizeof(strA)-1,strB,0,sizeof(strB)-1)<<endl;
    return 0;
}
